Exercise: Sorting Algorithms

Implement an updated version of the merge-sort algorithm.

We'll cover the following

Task

Task#

Implement a version of the merge-sort algorithm that sorts a DLList without using an auxiliary array.

Sample input

The sample input will be as follows:

5 2 9 1 3 6

Expected output

The expected output will be as follows:

Original List: 5 2 9 1 3 6 
Sorted List: 1 2 3 5 6 9

# Node class
class MergeSortDLLNode:
    def __init__(self, data):
        self.data = data
        self.prev = None
        self.next = None
# Merge sort class
class MergeSortDLL:
    # initialize function
    def __init__(self):
        self.head = None
    # Function to add value
    def add(self, data):
        # Write your code here
        pass
    # Merge sort function
    def merge_sort(self):
        # Write your code here
        pass
    # Helper function
    def _merge_sort(self, head):
        # Write your code here
        pass
    # Helper function
    def _merge(self, left, right):
        # Write your code here
        pass
    # Function to get middle value
    def _get_middle(self, head):
        if head is None:
            return None

Enter to Rename, Shift+Enter to Preview

Implementation of merge-sort using DLList

Discussion on Sorting Algorithms

Solution: Sorting Algorithms